/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.medium._34;

/**
 * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
 * <p>
 * 你的算法时间复杂度必须是 O(log n) 级别。
 * <p>
 * 如果数组中不存在目标值，返回 [-1, -1]。
 * <p>
 * 示例 1:
 * <p>
 * 输入: nums = [5,7,7,8,8,10], target = 8
 * 输出: [3,4]
 * 示例 2:
 * <p>
 * 输入: nums = [5,7,7,8,8,10], target = 6
 * 输出: [-1,-1]
 *
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.medium._34
 * @ClassName: SearchRange
 * @Author: linyaonan
 * @Date: 2020/4/2 15:48
 */
public class SearchRange {

    public int[] searchRange(int[] nums, int target) {
        int[] error = new int[]{-1, -1};
        // 异常情况
        if (nums == null || nums.length == 0) {
            return error;
        }
        int start = 0;
        int end = nums.length - 1;
        while (start <= end) {
            int mid = start + ((end - start) >> 1);
            if (nums[mid] >= target) {
                end = mid - 1;
            } else if (nums[mid] < target) {
                start = mid + 1;
            }
        }
        // 没找到
        if (start >= nums.length || nums[start] != target) {
            return error;
        }
        // 找到左边
        int left = start;
        while (start <= nums.length - 1) {
            if (nums[start] != target) {
                break;
            } else {
                start++;
            }
        }
        return new int[]{left, --start};
    }

    /**
     * 最左匹配，与最右匹配
     *
     * @param nums
     * @param target
     * @return
     */
    public int[] searchRange2(int[] nums, int target) {
        // 1. 异常边界
        if (nums == null || nums.length == 0) {
            return new int[]{-1, -1};
        }
        int rr = -1;
        // 2. 最左匹配
        {
            int l = 0;
            int r = nums.length - 1;


            while (l <= r) {
                int m = (l + r) >>> 1;
                int numM = nums[m];
                if (numM == target) {
                    rr = m;
                    r = m - 1;
                } else if (numM > target) {
                    r = m - 1;
                } else {
                    l = m + 1;
                }
            }

            if (rr == -1) {
                return new int[]{-1, -1};
            }
        }

        // 3. 最右匹配
        int rp = rr;
        {
            int l = rr;
            int r = nums.length - 1;
            while (l <= r) {
                int m = (l + r) >>> 1;
                int numM = nums[m];
                if (numM == target) {
                    l = m + 1;
                    rp = m;
                } else if (numM > target) {
                    r = m - 1;
                } else {
                    l = m + 1;
                }
            }
        }

        return new int[]{rr ,rp};
    }
}